package Top_Interview_Questions.Hash_Table;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/9 16:50
 * <p>
 * 功能描述:
 */
public class _0217 {

    /**
     * 有许多数据结构常用作动态集合,如二进制搜索树和哈希表。这里我们需要的操作是 search 和 insert。
     * 对于平衡二叉搜索树（Java 中的 TreeSet 或 TreeMap），search 和 insert 的时间复杂度均为
     * O(\log n)O(logn)。对于哈希表（Java 中的 HashSet 或 HashMap），search 和 insert 的平
     * 均时间复杂度为 O(1)O(1)。因此，通过使用哈希表，我们可以达到在线性时间复杂度解决问题。
     *
     */
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>(nums.length);
        for (int x: nums) {
            if (set.contains(x)) return true;
            set.add(x);
        }
        return false;
    }

}
